With the development of high performance portable personal computers and the necessity for networking among various computing machines, wireless local area network (LAN) has become an important emerging issue facing today's information industry. A successful implementation of the wireless LAN involves, among other things, a successful establishment of physical layer transmissions (PHY) through radio or infrared, and an effective as well as productive medium access control protocol (MAC).
Wireless LAN usually allows two types of realizations: infrastructured LANs and ad-hoc LANs. For most applications of wireless LANs, however, a certain kind of infrastructure is still required no matter if it is a radio LAN, or an IR (infrared) LAN. Such an infrastructure is typically a wired or wireless backbone, and the network traffic is divided into two directions: uplink (into the backbone) and downlink (from the network). The contact points for backbone with wireless medium (i.e., air) are called access points. The access points can be base stations or repeaters to enlarge the coverage of communication.
Due to the special feature of wireless LANs, a common channel is utilized to all access points and mobile nodes, and the downlink communication is typically achieved by broadcasting. On the other hand, uplink traffic generally needs a multiple access control protocol to handle the transmissions from all the active mobile nodes. There exist several reasons that make the uplink traffic difficult for wireless LANs. These include: (1) wireless LANs typically operate in very strong multipath fading channels which can change their characteristics in a very short time or in a very short distance (spatial domain); (2) the wireless medium is quite different from the cable and/or optical fiber medium, and many trivial implementations in wired medium, such as carrier sensing, are not so trivial for wireless medium; (3) wireless LANs are designed to serve mobile users who are expected to move around from one part of the network to another, and new users may be expected to join the LAN at any time and any place; and (4) wireless LANs may introduce spatial domain behavior due to the multicell structure, and a handoff must be properly handled Due to these difficulties, uplink access control protocol has become an important task for the MAC design of wireless LANs. An efficient and productive MAC protocol based on random access control is desired and indeed needed for wireless LANs since, as described before, new mobile nodes may join the network at any time or any place. An efficient random access protocol is also desired to serve new traffic into the network.
The IEEE project 802 has formed study group 802.11 to set up a new international wireless LAN standard. During the process of the IEEE 802.11 standards recommendation, 20 problematic areas (requirements) have been identified in selecting a decent MAC protocol. These include: throughput; delay; transparency to different PHY layers; ability to serve data, voice, and video (time bounded services); fairness of access; battery powered communication; maximum number of nodes; robustness with respect to collocated networks; ability to support handoff/roaming between service areas; establishment of peer-to-peer connectivity without prior knowledge; unauthorized network access impact on throughput; ability to support broadcast (multicast); critical delay which may limit large area coverage; MAC needs to enforce insensitivity to capture effects; support for priority traffic; ability to support non-reciprocal traffic; preservation of MSDU's order; ability to work in simple, small and large systems; implication on complexity of PHY; and ability to market and complexity. Regarding to throughput, with 10M bps physical transmission and over 80% throughput for CSMA/CD, Ethernet can deliver over 8M bps performance in principle. By comparison, only 3-3.5M bps performance is achieved for wireless LANs.
Many protocols based on token passing carrier sensing, and ALOHA, have been proposed for wireless LANs with infrastructure. They all present some difficulties to be considered an ideal solution for wireless LANs. Other protocols such as CDMA or B-CDMA are, in practice, hard to achieve for situations requiring high rate data transmissions, due to the limitations of available spectrum and the relatively rudimentary base stations of most LAN applications. More recently, a medium access control protocol based on randomly addressed polling was proposed by the coinventors of the present invention for multi-cell, high speed wireless networks. A performance analysis of their proposed protocol was provided in a publication entitled: "Performance Analysis of Randomly Addressed Polling". This paper was presented at the Fourth International Symposium n Person, Indoor and Mobile Radio Communications (PIMRC"93), Yokohama, Japan (Sep. 8-11, 1993). The content disclosed therein is hereby expressly incorporated by reference. Their proposed protocol, named "RAP" (which stands for randomly addressed polling), is a centralized MAC protocol with partial decentralized functions such as initiation of handoff. It is aimed at controlling up-link traffic during wireless LAN data communication between a base station and mobile nodes. The randomly addressed polling protocol developed by the co-inventors has been demonstrated to show good throughput and delay statistics, no handoff for data services, soft handoff for time-bounded services, fairness to access; is transparent to many widely used transmissions; and provides seamless service in multi-cell wireless networks as well as supports multi-cast function.
However, while the randomly addressed polling protocol has met many of the requirements for wireless LANs and appeared to be an attractive protocol for wireless networks, it has been observed that the delay in packet data transmission is very sensitive to the arrival rate when the arrival rate approaches the optimal rate, i.e., the delay associated with the protocol becomes unstable (jumps up and down) about the average delay. Furthermore, it was also observed that the randomly addressed polling protocol would suffer repeated collisions at a random address, when only a limited number of random addresses are provided and the number of active users (i.e., active mobile nodes) is large.